package fun.ticsmyc.graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

/**
 * 最短路径算法：Dijkstra
 * 与Prim类似， Prim保存的是其他点到生成树上任意一点的距离， 而Dijkstra保存的是其他点到起始点的距离

 * @author Ticsmyc
 * @package fun.ticsmyc.graph
 * @date 2021-01-30 17:04
 */
public class Dijkstra {

    //3112. 访问消失节点的最少时间  标准dijkstra加个特殊判断
    public int[] minimumTime(int n, int[][] edges, int[] disappear) {
        //1. 维护边关系
        List<int[]>[] adj = new List[n];
        for (int i = 0; i < adj.length; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            adj[edge[0]].add(new int[]{edge[1],edge[2]});
            adj[edge[1]].add(new int[]{edge[0],edge[2]});
        }
        //2.记录可达的点 且按距离排序
        PriorityQueue<int[]> queue = new PriorityQueue<>((a,b)->a[1]-b[1]);

        int[] res = new int[n];
        Arrays.fill(res,-1);
        res[0]=0;

        queue.add(new int[]{0,0});
        while(!queue.isEmpty()){
            //3. 每次从可达的点里取出距离最近的一个
            int[] poll = queue.poll();
            int from = poll[0];
            int dis = poll[1];

            //4. 如果已经走过 跳过
            if(res[from] < dis){
                continue;
            }

            //5. 目标点的目标点也可达了
            for (int[] ints : adj[from]) {
                int target = ints[0];
                int targetDis = dis+ints[1];
                //6. 没走过 或 走过但这次更近
                if(disappear[target] > targetDis && (res[target] ==-1 || res[target] > targetDis)){
                    res[target] = targetDis;
                    queue.add(new int[]{target,targetDis});
                }
            }
        }
        return res;
    }


    //  778. 水位上升的泳池中游泳
    public int swimInWater(int[][] grid) {
        int n = grid.length;
        int[][] go = new int[][]{{-1,0},{1,0},{0,1},{0,-1}};
        boolean[][] visited = new boolean[n][n];
        PriorityQueue<Node> queue = new PriorityQueue<>((a, b)->a.dis-b.dis);

        visited[0][0] = true; //起始点
        queue.add(new Node(1,0,Math.max(grid[0][0],grid[1][0])));
        queue.add(new Node(0,1,Math.max(grid[0][0],grid[0][1])));
        int ans = 0;
        while(!queue.isEmpty()){
            Node cur = queue.poll();
            if(!visited[cur.i][cur.j]){
                visited[cur.i][cur.j] = true;
                ans = Math.max(ans,cur.dis);
                if(cur.i==n-1 && cur.j == n-1){
                    break;
                }
                for(int i=0;i<go.length;++i){
                    if(cur.i+go[i][0] >=0 && cur.i+go[i][0]<n && cur.j+go[i][1] >=0 && cur.j+go[i][1]<n && !visited[cur.i+go[i][0]][cur.j+go[i][1]]){
                        queue.add(new Node(cur.i+go[i][0],cur.j+go[i][1],Math.max(cur.dis,grid[cur.i+go[i][0]][cur.j+go[i][1]])));
                    }
                }

            }
        }
        return ans;
    }

    private class Node{
        int i;
        int j;
        int dis; //淹没这个点所需的时间
        public Node(int ii, int jj, int dist){
            this.i = ii;
            this.j = jj;
            this.dis = dist;
        }
    }
}
